/**
 * 538. 把二叉搜索树转换为累加树
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 */
const {
  displayTreeNode,
  createTreeNode,
} = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {number} base
 * @return {number}
 */
function convertSub(root, base) {
  if (root.right) {
    root.val += convertSub(root.right, base);
  } else {
    root.val += base;
  }
  if (root.left) {
    return convertSub(root.left, root.val);
  }
  return root.val;
}

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function convertBST(root) {
  if (!root) {
    return root;
  }
  convertSub(root, 0);
  return root;
}

console.log(
  displayTreeNode(convertBST(createTreeNode([4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8])))
  === '[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]',
);
console.log(
  displayTreeNode(convertBST(createTreeNode([0, null, 1])))
  === '[1,null,1]',
);
console.log(
  displayTreeNode(convertBST(createTreeNode([1, 0, 2])))
  === '[3,3,2]',
);
console.log(
  displayTreeNode(convertBST(createTreeNode([3, 2, 4, 1])))
  === '[7,9,4,10]',
);
